home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 145 / Gekkan Dennou Club - 2000.6 Vol. 145 (Japan) (Track 1).bin / docs / perl / avltree.pm < prev    next >
Encoding:
Text File  |  2000-04-22  |  3.4 KB  |  164 lines
  1. #
  2. # avltree.pl : ＡＶＬ平衡木（二分探索木を継承）
  3. #
  4. #
  5. use Bintree;
  6.  
  7. package Avltree;
  8. @ISA = (Bintree);
  9.  
  10. # $nil の取得
  11. sub make_tree {
  12.   $nil = Bintree->make_tree();
  13.   bless $nil, 'Avltree';
  14.   $nil;
  15. }
  16.  
  17. # 節を作る
  18. sub new {
  19.   my ($type, $item) = @_;
  20.   my $obj = {
  21.     'item'    => $item,
  22.     'left'    => $nil,
  23.     'right'   => $nil,
  24.     'balance' => 0
  25.   };
  26.   bless $obj, $type;
  27.   $obj;
  28. }
  29.  
  30. # データの追加
  31. sub insert_tree {
  32.   my ($root, $item) = @_;
  33.   my @stack = ();
  34.   my $place = \$root;
  35.   while( $$place != $nil ){
  36.     my $node = $$place;
  37.     my $result = $item->compare( $node->{'item'} );
  38.     push( @stack, $node );
  39.     if( $result == 0 ){
  40.       return $root;       # 同じデータ有り
  41.     } elsif( $result < 0 ){
  42.       $place = \$node->{'left'};
  43.     } else {
  44.       $place = \$node->{'right'};
  45.     }
  46.   }
  47.   # データの挿入
  48.   my $obj = Avltree->new($item);
  49.   return $obj if $root == $nil;  # ルートに挿入
  50.   $$place = $obj;
  51.   &check_balance( $root, $obj, \@stack );
  52. }
  53.  
  54.  
  55. # バランスのチェック
  56. sub check_balance {
  57.   my ($root, $node, $stack) = @_;
  58.   my $cnode = $nil;
  59.   my ($b, $pnode);
  60.  
  61.   for( ; @$stack > 0; $node = $pnode ){
  62.     $pnode = pop( @$stack );
  63.     if( $pnode->{'left'} == $node ){
  64.       $b = ++$pnode->{'balance'};
  65.     } else {
  66.       $b = --$pnode->{'balance'};
  67.     }
  68.     return $root if $b == 0;    # 書き換え必要無し
  69.     if( $b > 1 ){
  70.       $cnode = &LR_rotate( $node, $pnode );
  71.       last;
  72.     } elsif( $b < -1 ) {
  73.       $cnode = &RL_rotate( $node, $pnode );
  74.       last;
  75.     }
  76.   }
  77.   # 子の付け替え処理
  78.   if( @$stack > 0 ){
  79.     my $ppnode = pop( @$stack );
  80.     if( $ppnode->{'left'} == $pnode ){
  81.       $ppnode->{'left'} = $cnode;
  82.     } else {
  83.       $ppnode->{'right'} = $cnode;
  84.     }
  85.   } elsif( $cnode != $nil ){
  86.     # ルートの変更
  87.     return $cnode;
  88.   }
  89.   $root;
  90. }
  91.  
  92. # LR 回転
  93. sub LR_rotate {
  94.   my ($node, $pnode) = @_;
  95.   my $cnode;
  96.  
  97.   if( $node->{'balance'} < 0 ){
  98.     # LR2
  99.     $cnode = $node->{'right'};
  100.     $pnode->{'left'} = $cnode->{'right'};
  101.     $node->{'right'} = $cnode->{'left'};
  102.     $cnode->{'right'} = $pnode;
  103.     $cnode->{'left'} = $node;
  104.     if( $cnode->{'balance'} > 0 ){
  105.       $pnode->{'balance'} = -1;
  106.       $node->{'balance'} = 0;
  107.     } elsif( $cnode->{'balance'} < 0 ){
  108.       $pnode->{'balance'} = 0;
  109.       $node->{'balance'} = 1;
  110.     } else {
  111.       $pnode->{'balance'} = 0;
  112.       $node->{'balance'} = 0;
  113.     }
  114.     $cnode->{'balance'} = 0;
  115.   } else {
  116.     # LL1
  117.     $pnode->{'left'} = $node->{'right'};
  118.     $node->{'right'} = $pnode;
  119.     $pnode->{'balance'} = 0;
  120.     $node->{'balance'} = 0;
  121.     $cnode = $node;
  122.   }
  123.   $cnode;
  124. }
  125.  
  126. # RL 回転
  127. sub RL_rotate {
  128.   my ($node, $pnode) = @_;
  129.   my $cnode;
  130.  
  131.   if( $node->{'balance'} > 0 ){
  132.     # RL2
  133.     $cnode = $node->{'left'};
  134.     $pnode->{'right'} = $cnode->{'left'};
  135.     $node->{'left'} = $cnode->{'right'};
  136.     $cnode->{'left'} = $pnode;
  137.     $cnode->{'right'} = $node;
  138.     if( $cnode->{'balance'} > 0 ){
  139.       $node->{'balance'} = -1;
  140.       $pnode->{'balance'} = 0;
  141.     } elsif( $cnode->{'balance'} < 0 ){
  142.       $node->{'balance'} = 0;
  143.       $pnode->{'balance'} = 1;
  144.     } else {
  145.       $node->{'balance'} = 0;
  146.       $pnode->{'balance'} = 0;
  147.     }      
  148.     $cnode->{'balance'} = 0;
  149.   } else {
  150.     # RR1
  151.     $pnode->{'right'} = $node->{'left'};
  152.     $node->{'left'} = $pnode;
  153.     $pnode->{'balance'} = 0;
  154.     $node->{'balance'} = 0;
  155.     $cnode = $node;
  156.   }
  157.   $cnode;
  158. }
  159.  
  160.  
  161. 1;
  162.  
  163. # end of file
  164.